package com.lfg.leetcode.leetcode0;

/**
 * 算法思想：
 * 1.从数列的右边向左寻找连续递增序列, 例如对于：1,3,5,4,2，其中5-3-2即为递增序列。
 * 2.从上述序列中找一个比它前面的数（3）大的最小数（4），并将且交换这两个数。于是1,3,5,4,2->1,4,5,3,2，此时交换后的依然是递增序列。
 * 3.新的递增序列逆序，即：1,4,5,3,2 => 1,4,2,3,5
 */

public class No31NextPermutation {

    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        for (; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i < 0) {
            quickSort(nums, 0, nums.length - 1);
            return;
        }
        int j = nums.length - 1;
        int min = nums[i];

        Integer t = null;
        while (i < j) {
            if (nums[j] > min && (t == null || nums[j] < nums[t])) {
                t = j;
            }
            j--;
        }
        if (t == null) {
            swap(nums, i, i + 2);
        } else {
            swap(nums, i, t);
        }
        quickSort(nums, i + 1, nums.length - 1);
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }

    public static int[] quickSort(int[] nums, int i, int j) {
        int middle = (i + j) / 2;
        int n = i;
        int m = j;
        while (i < j) {
            while (i < middle && nums[i] <= nums[middle]) {
                i++;
            }
            if (i < middle) {
                swap(nums, i, middle);
                middle = i;
            }
            while (j > middle && nums[j] >= nums[middle]) {
                j--;
            }
            if (j > middle) {
                swap(nums, j, middle);
                middle = j;
            }
        }
        if (n >= m) {
            return nums;
        }
        quickSort(nums, n, middle);
        quickSort(nums, middle + 1, m);
        return nums;
    }

    public static void main(String[] args) {
//        int[] nums = {3, 2, 1};
//        int[] nums = {1, 3, 2};
        int[] nums = {2, 2, 7, 5, 4, 3, 2, 2, 1};
//        int[] nums = {43, 4};
//        int[] nums = {1, 3, 2, 3, 3, 2, 2, 3, 9, 4, 5, 6, 7, 8};
        nextPermutation(nums);

//        quickSort(nums, 0, nums.length - 1);
        for (int i : nums) {
            System.out.println(i);
        }
    }
}

